package com.wyr.leetcode.step2.array;

import java.util.Arrays;

/**
 * 16. 最接近的三数之和
 * <p>
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * <p>
 * 返回这三个数的和。
 * <p>
 * 假定每组输入只存在恰好一个解。
 * <p>
 * https://leetcode.cn/problems/3sum-closest/description/?envType=problem-list-v2&envId=array
 */
public class ThreeSumClosestTest {

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        threeSumClosest(nums, 1);
    }

    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int best = Integer.MAX_VALUE;
        int k = 0;
        while (k < nums.length - 2) {
            if (k > 0 && nums[k - 1] == nums[k]) {
                k++;
                continue;
            }
            // 改进1
            /**
             * 设 s = nums[i] + nums[i+1] + nums[i+2]。
             * 如果 s > target，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，
             * 所以不会找到比 s 更优的答案了。所以只要 s > target，就可以直接 break 外层循环了。
             * 在 break 前判断 s 是否离 target 更近，如果更近，那么更新 best 为 s。
             */
            if (nums[k] + nums[k + 1] + nums[k + 2] > target) {
                if (Math.abs(nums[k] + nums[k + 1] + nums[k + 2] - target) < Math.abs(best - target)) {
                    best = nums[k] + nums[k + 1] + nums[k + 2];
                }
                break;
            }
            int i = k + 1;
            int j = nums.length - 1;
            while (i < j) { // i，j不相遇
                // 改进2:
                /**
                 * 原理同改进1
                 */
                if (nums[k] + nums[i] + nums[i+1] > target) {
                    if (Math.abs(nums[k] + nums[i] + nums[i+1] - target) < Math.abs(best - target)) {
                        best = nums[k] + nums[i] + nums[i+1];
                    }
                    break;
                }

                if (nums[k] + nums[i] + nums[j] == target) {
                    return target;
                } else {
                    if (Math.abs(nums[k] + nums[i] + nums[j] - target) < Math.abs(best - target)) {
                        best = nums[k] + nums[i] + nums[j];
                    }

                    if (nums[i] + nums[j] > target - nums[k]) {
                        // 如果和大于 target，移动 c 对应的指针
                        int j0 = j - 1;
                        // 移动到下一个不相等的元素
                        while (j0 > i && nums[j0] == nums[j]) {
                            --j0;
                        }
                        j = j0;
                    } else {
                        // 如果和小于 target，移动 b 对应的指针
                        int i0 = i + 1;
                        // 移动到下一个不相等的元素
                        while (i0 < j && nums[i0] == nums[i]) {
                            ++i0;
                        }
                        i = i0;
                    }
                }
            }
            k++;// k别忘了自增
        }
        return best;
    }
}
